﻿// 面试题 17.05. 字母与数字.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <vector>
#include <unordered_map>


using namespace std;
/*
https://leetcode.cn/problems/find-longest-subarray-lcci/description/

给定一个放有字母和数字的数组，找到最长的子数组，且包含的字母和数字的个数相同。

返回该子数组，若存在多个最长子数组，返回左端点下标值最小的子数组。若不存在这样的数组，返回一个空数组。

示例 1:

输入: ["A","1","B","C","D","2","3","4","E","5","F","G","6","7","H","I","J","K","L","M"]

输出: ["A","1","B","C","D","2","3","4","E","5","F","G","6","7"]


示例 2:
输入: ["A","A"]
输出: []


提示：
array.length <= 100000
*/


class Solution {
public:
    unordered_map<int, int> mm;
    vector<string> findLongestSubarray(vector<string>& array) {
        int presum[100010]; memset(presum, 0, sizeof presum);
        array.insert(array.begin(), "#");

        for (int i = 1; i < array.size(); i++) {
            presum[i] = presum[i - 1];
            if (array[i][0] >= '0' && array[i][0] <= '9') {
                presum[i]++;
            }
            else {
                presum[i]--;
            }
        }
        int ans = 0; mm[0] = 0;
        int l = -1, r = -1;
        for (int i = 0; i < array.size(); i++) {
            if (mm.count(presum[i]) == 0) mm[presum[i]] = array.size() + 1;
            //ans = max(ans, i - mm[presum[i]]);
            if (ans < i - mm[presum[i]]) {
                ans = i - mm[presum[i]];
                l = mm[presum[i]]; r = i;
            }
            mm[presum[i]] = min(mm[presum[i]], i);
        }
        if (l == -1 || r == -1) return vector<string>();
        return vector<string>(array.begin()+l+1,array.begin()+r+1);
    }
};

int main()
{
    Solution s;
    vector<string> v{
        //"A","1","B","C","D","2","3","4","E","5","F","G","6","7","H","I","J","K","L","M"
        "A","A",
    };
    vector<string> ret = s.findLongestSubarray(v);
    for (auto e : ret) {
        cout << e << " ";
    }
	return 0;
}

 